package test3.recursion;

public class Fibonacci {
    public static void main(String[] args) {

        int fibonacci = new Fibonacci().fibonacci(45);
        System.out.println(fibonacci);

    }

    public int fibonacci(int n) {
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        return (fibonacci(n - 1) + fibonacci(n - 2)) % 1000000007;
    }

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int constant = 1000000007;
        int sum1 = 0;
        int sum2 = 1;
        int sum = 0;
        int i = 2;
        while (i <= n) {
            sum = (sum1 + sum2) % constant;
            sum1 = sum2 ;
            sum2 = sum;
            i++;
        }
        return sum % constant;
    }
}
